package day_8_18;

import java.util.HashMap;
import java.util.List;

/**
 * 2841. 几乎唯一子数组的最大和
 * https://leetcode.cn/problems/maximum-sum-of-almost-unique-subarray/description/
 */
public class Main3 {
    public long maxSum(List<Integer> nums, int m, int k) {
        // 这个问题最主要的就是对于 子数组中数字出现次数的统计
        // 使用 HashMap 来统计出现的次数
        HashMap<Integer,Integer> map = new HashMap<>();
        // 记录当前窗口中不同数字的个数
        int count = 0;
        // 用来统计当前窗口的和
        long sum = 0;
        // 返回的就是最大的值
        long ret = 0;
        int n = nums.size();
        for(int i = 0;i < n;i++) {
            // 1、入窗口
            sum += nums.get(i);
            // 再将出现的数字放入到 HashMap 中，进行统计出现的次数，为了后序进行判断是否是第一个出现，和出窗口做准备
            map.put(nums.get(i),map.getOrDefault(nums.get(i),0) + 1);
            // 进行判断是否第一次出现，如果是次数就+1
            if(map.get(nums.get(i)) == 1) {
                count++;
            }

            // 2、判断窗口是否符合长度
            if(i < k - 1) {
                continue;
            }

            // 3、判断是否可以更新数据
            // 只有当 当前窗口中不同数字的个数 大于等于 m 才能更新
            if(count >= m) {
                ret = Math.max(ret,sum);
            }

            // 4、出窗口
            sum -= nums.get(i - (k - 1));
            // 将这个出去的数据对应的 map 中的次数-1
            map.put(nums.get(i - (k - 1)),map.get(nums.get(i - (k - 1))) - 1);
            // 如果减完之后，这个数据对应的map中的值为0的话，那么说明 当前窗口中不同数字的个数 需要-1
            if(map.get(nums.get(i - (k - 1))) == 0) {
                count--;
            }
        }
        return ret;
    }
}
